/*
 *  Copyright 2021 籽籮籮 籵籮籮籯类籲籷籰
 *  This includes Copyright (C) 2008, 2011 Matthias Stallmann, Saurabh Gupta.
 *  See also https://github.com/mfms-ncsu
 *  This includes splay Copyright (C) 1998-2021 Free Software Foundation, Inc.
 *  This includes Copyright (C) 2009 MiptVis GNU GPL version 3+ Boris Shurygin
 *  Junio H Hamano gitster@pobox.com
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * SPDX-License-Identifier: GPL-3.0+
 * License-Filename: LICENSE
 */

/* hierarchy routines. */

#include "config.h"

#include <stdio.h>
#include <string.h>

#include "splay-tree.h"
#include "main.h"
#include "hier.h"
#include "dpmem.h"
#include "uniqstr.h"
#include "uniqnode.h"
#include "rhp.h"

/* the graph data rootgraph */
struct gml_graph *maingraph = NULL;

/* add node with node name and optional label */
void add_new_node(struct gml_graph *g, struct gml_graph *ro, int nr, int foundid, char *nodename, char *nodelabel, int ncolor, int nbcolor, struct gml_rl *rlabel, struct gml_hl *hlabel, int fontcolor, int ishtml)
{
    struct gml_node *node = NULL;
    struct gml_nlist *lnll = NULL;
    char nlbuf[32];

    printf("%s(): adding node %d foundid=%d \"%s\" with label \"%s\"\n", __func__, nr, foundid, nodename, nodelabel);

    /* the optional label is node number or specified label */
    if (!nodelabel) {
	memset(nlbuf, 0, 32);
	/* no specified node label, so use the id of the node. */
	snprintf(nlbuf, (32 - 1), "%d", foundid);
    }

    /* add here check for double defined nodes */

    node = dp_calloc(1, sizeof(struct gml_node));

    /* layouter number */
    node->nr = nr;

    /* gml number */
    node->id = foundid;

    node->name = uniqstr(nodename);

    if (nodelabel) {
	/* label is the specified label */
	node->nlabel = uniqstr(nodelabel);
    } else {
	/* label is the numeric string of the node id. */
	node->nlabel = uniqstr(nlbuf);
    }

    lnll = dp_calloc(1, sizeof(struct gml_nlist));

    lnll->node = node;

    if (g->rawnodelist == NULL) {
	g->rawnodelist = lnll;
	g->rawnodelisttail = lnll;
    } else {
	g->rawnodelisttail->next = lnll;
	g->rawnodelisttail = lnll;
    }

    /* number of nodes in this graph */
    g->nnodes++;

    /* add uniq node by internal number and uniq gml number */
    uniqnode_add(g, node);

    return;
}

/* the numbers are the gml numbers. */
void add_new_edge(struct gml_graph *g, struct gml_graph *ro, int foundsource, int foundtarget, char *elabel, int ecolor, int style, char *fcompass, char *tcompass, int constraint, int ishtml)
{
    struct gml_edge *edge = NULL;
    struct gml_elist *el = NULL;
    struct gml_node *snode = NULL;
    struct gml_node *tnode = NULL;

    printf("%s(): adding edge from %d to %d\n", __func__, foundsource, foundtarget);

    /* add here the check if nodes are define with uniqnode() */
    snode = uniqnodeid(g, foundsource);

    if (!snode) {
	/* shouldnothappen */
	printf("%s(): source node with number %d not found\n", __func__, foundsource);
	return;
    }

    tnode = uniqnodeid(g, foundtarget);

    if (!tnode) {
	/* shouldnothappen */
	printf("%s(): target node with number %d not found\n", __func__, foundtarget);
	return;
    }

    /* a new edge */
    edge = dp_calloc(1, sizeof(struct gml_edge));

    /* edge number start at 1 */
    g->edgenum++;
    edge->nr = g->edgenum;

    /* from/to nodes */
    edge->from_node = tnode;
    edge->to_node = snode;

    /* set optional edge label */
    if (elabel) {
	/* number of edge labels */
	g->nedgelabels++;
	edge->elabel = uniqstr(elabel);
    }

    /* */
    el = dp_calloc(1, sizeof(struct gml_elist));

    el->edge = edge;

    if (g->rawedgelist == NULL) {
	g->rawedgelist = el;
	g->rawedgelisttail = el;
    } else {
	g->rawedgelisttail->next = el;
	g->rawedgelisttail = el;
    }

    /* number of edges in this subgraph */
    g->nedges++;

    return;
}

/* delete edge */
void del_edge(struct gml_graph *g, struct gml_elist *edgeel)
{
    /* changed: not delete edge but put it in another edge list
     * these edges can be used later on
     * put it into dedgelist and unlink from main edgelist
     */
    return;
}

/* prepare for all-at-once graph layout */
void prep(struct gml_graph *g)
{
    struct gml_nlist *lnl = NULL;
    struct gml_elist *enl = NULL;

    /* add here write file with the raw parsed data */

    printf("%s(): layouter data:\n", __func__);
    lnl = g->rawnodelist;
    while (lnl) {
	printf("  node %d\n", lnl->node->nr);
	lnl = lnl->next;
    }

    enl = g->rawedgelist;
    while (enl) {
	printf("  edge %d\n", enl->edge->nr);
	enl = enl->next;
    }

    /* create work list */

    /* for this just set pointers */
    g->nodelist = g->rawnodelist;
    g->nodelisttail = g->rawnodelisttail;
    g->edgelist = g->rawedgelist;
    g->edgelisttail = g->rawedgelisttail;

    return;
}

/* prepare the data about edge labels */
void prepel(struct gml_graph *g)
{
    struct gml_elist *enl = NULL;
    printf("%s(): graph has %d edges with a label\n", __func__, g->nedgelabels);
    /* number of edge labels */
    if (g->nedgelabels == 0) {
	/* can be skipped if there are no edge labels */
	return;
    }
    enl = g->edgelist;
    while (enl) {
	/* this is a ege with edge label */
	if (enl->edge->elabel) {
	    /* create extra data about this edge with edge label to use later on */
	}
	enl = enl->next;
    }
    return;
}

#if 0
for (list < pLNode >::iterator node_iter = m_nodes_list.begin(); node_iter != m_nodes_list.end(); node_iter++) {
    start with node in input if ((*isused)[*node_iter] == false) {
	// Starts from every new node.
	DFS((*node_iter), isused, dfs, &num);
    }
}
#endif

//static void uncycledfs ()

/* remove cycles in the graph */
void uncycle(struct gml_graph *g)
{
    struct gml_nlist *lnll = NULL;

    /* run dfs to mark edges to reverse */
    /* after that do actual reverse of the edges */
    /* indicate the start nodes now with no incoming edges */

    /* build the s/t list of a node */
    clear_stlist_all(g);
    make_stlist(g);

    /* init */
    lnll = g->nodelist;
    while (lnll) {
	lnll->node->y = -1;
	lnll->node->done = 0;
	lnll->node->grey = 0;
	lnll = lnll->next;
    }

    /* notice that the raw input graph can have no starter nodes. as in 1->2->3->1 */

    /* run dfs */
    lnll = g->nodelist;
    while (lnll) {
	/* not set */
	if (lnll->node->y < 0) {
	    /* run dfs on starter nodes */
	    if (lnll->node->indegree == 0) {

	    }
	}
	lnll = lnll->next;
    }

    /* run dfs */
    lnll = g->nodelist;
    while (lnll) {
	/* not set */
	if (lnll->node->y < 0) {
	    /* run dfs on remaining nodes */
	}
	lnll = lnll->next;
    }

    /* now revert the indicated edges */

    return;
}

/* set relative y level of all nodes */
void ylevels(struct gml_graph *g)
{
    /* run dfs to set the relative y level.
     * start with the nodes which are start nodes
     */
    return;
}

/* check for same edges as 1->2 and 1->2 
 * set count in main graph
 * indicate nodes part of same edges
 * indicate edges part of same edges
 */
void checksame(struct gml_graph *g)
{
    struct gml_nlist *lnll = NULL;
    struct gml_elist *oute = NULL;
    struct gml_elist *oute2 = NULL;
    struct gml_node *curn = NULL;
    struct gml_elist *enl = NULL;
    int flag = 0;

    /* check outgoing edges of nodes */
    lnll = g->nodelist;
    while (lnll) {
	oute = lnll->node->outgoing_e;
	while (oute) {
	    /* edge which is not done yet */
	    if (oute->edge->same == 0) {
		/* indicate original edge as same */
		flag = 0;
		/* current to node in this edge to check. */
		curn = oute->edge->to_node;
		oute2 = oute->next;
		while (oute2) {
		    /* at 1->1 */
		    if (oute2->edge->to_node == curn) {
			/* this is a same edge. */
			oute2->edge->same = 1;
			/* indicate it in the nodes */
			oute2->edge->to_node->same = 1;
			oute2->edge->from_node->same = 1;
			/* indicate the original edge */
			flag = 1;
		    }
		    oute2 = oute2->next;
		}
		/* indicate original edge as same */
		if (flag) {
		    /* this is a same edge. */
		    oute->edge->same = 1;
		    /* indicate it in the nodes */
		    oute->edge->to_node->same = 1;
		    oute->edge->from_node->same = 1;
		}
	    }
	    oute = oute->next;
	}
	lnll = lnll->next;
    }

    /* refresh same edges count */
    g->nsame = 0;

    enl = g->edgelist;
    while (enl) {
	if (enl->edge->same) {
	    g->nsame++;
	}
	enl = enl->next;
    }

    printf("%s(): this graph has %d same edges\n", __func__, g->nsame);

    return;
}

/* run barycenter using rhp.c from matthias stallman */
void barycenter(struct gml_graph *g, int it1val, int it2val)
{
    struct gml_nlist *lnll = NULL;
    struct gml_elist *enl = NULL;
    int status = 0;

    /* copy data to rhp.c and run and copy result back */
    printf("%s(): running rhp.c barycenter\n", __func__);

    /* copy node data into barycenter */
    lnll = g->nodelist;
    while (lnll) {
	/* get node number and relative y level with optional extra data */
	lnll = lnll->next;
    }

    /* copy edge data into barycenter */
    enl = g->edgelist;
    while (enl) {
	/* get edge number with from and to node and optional extra data */
	enl = enl->next;
    }

    /* init, log file */
    rhp_init( /* log file name */ (char *)"", /* 1=debug output */ 1);

    /* demo how to add some data */
    status = rhp_addnode(1 /* num */ , 0 /* level */ , NULL /* void *data */ );
    status = rhp_addnode(2 /* num */ , 1 /* level */ , NULL /* void *data */ );
    status = rhp_addedge(1 /* num */ , 1 /* fnode */ , 2 /* tnode */ , NULL /* void *data */ );
    rhp_layout(0 /* options */ , 0 /* nodeweightadjust */ );

    /* run this to get the result of this graph layout
     * extern int rhp_node_foreach(int (*getnodedata)(int num, int level, int pos, void *data));
     * extern int rhp_edge_foreach(int (*getedgedata)(int num, int fnum, int flevel, int fpos, int tnum, int tlevel, int tpos, int64_t ecross, void *data));
     */

    /* free all memory when ready with rhp.c */
    rhp_deinit();

    return;
}

/* doublespace the vertical levels */
void doublespaceyafter(struct gml_graph *g)
{
    printf("%s():\n", __func__);
    /* after barycenter, add levels with only dummy nodes */
    return;
}

/* split longer edges */
void splitedgesafter(struct gml_graph *g)
{
    printf("%s():\n", __func__);
    /* if edge length is > 1 then
     * replace this edge with
     * fake nodes each with distance 1
     * for already splitted edges at
     * same edges do it different.
     */
    return;
}

/* add edgelabels */
void edgelabelsafter(struct gml_graph *g)
{
    printf("%s():\n", __func__);
    /* at edges with edge label, replace the middle node with a edge label text node
     * option here to put the edge label at other position and/or to skip edgelabels.
     * often edge labels are not very usable and to turn it off gives a better drawing
     */
    return;
}

/* improve_positionsbk_edgetypes() run modified edge crossing count algorithm and indicate the different edge types */
/* improve_positionsbk()
 improve_positionsbk_edgetypes()
 improve_positionsbk_4pos()
 improve_positionsbk_moveblocks()
 improve_positionsbk_finalxy()
*/

/* run positioning */
void improve_positions(struct gml_graph *g)
{
    printf("%s():\n", __func__);
    /* add here own algorithm as easy as possible or as complex as needed
     * see also igraph c library sugiyama.c
     * see also d3 dagre javascript lib
     * see also elk java lib
     * see also ogdf c++ lib
     * see also multiple pdf's about the errors in the bk algorithm
     * the bk algorithm needs updates to handle nodes with variable (x,y) sizes
     * also consider other algorithms
     * indicate type of edges and the sub parts
     * determine 4 possible positionings
     * positioning the sub parts
     */
    /* improve_positionsbk() */
    return;
}

/* do additional edge line routing */
void edgerouting(struct gml_graph *g)
{
    printf("%s():\n", __func__);
    /* this can be done easy but then the result is not as good
     * or add huge amounts of source for spline edge routing.
     * but even then the edges may not as good as expected.
     */
    return;
}

/* create some image, svg, png or other */
void createimage(struct gml_graph *g)
{
    printf("%s():\n", __func__);
    /* write out the needed data as textual data, json, xml
     * and let another program do the drawing, or generate
     * here pdf, svg, or limited size jpg or png or otherwise
     */
    return;
}

/* rebuild nodes st lists
 * this is the data of incoming and outgoing edges
 */
void make_stlist(struct gml_graph *g)
{
    struct gml_nlist *lnll = NULL;
    struct gml_elist *enl = NULL;
    struct gml_elist *ne = NULL;

    /* refresh degree count of nodes */
    lnll = g->nodelist;
    while (lnll) {
	/* make sure these are cleared */
	lnll->node->outgoing_e = NULL;	/* source list, outgoing edges */
	lnll->node->outgoing_etail = NULL;	/* source list, outgoing edges */
	lnll->node->incoming_e = NULL;	/* target list, incoming edges */
	lnll->node->incoming_etail = NULL;	/* target list, incoming edges */
	lnll->node->indegree = 0;
	lnll->node->outdegree = 0;
	lnll->node->done = 0;
	lnll->node->grey = 0;
	lnll = lnll->next;
    }

    /* the lists with incoming nd outgoing edges are kept simple as linked lists */
    enl = g->edgelist;
    while (enl) {

	ne = dp_calloc(1, sizeof(struct gml_elist));

	ne->edge = enl->edge;

	/* list of outgoing edges */
	if (enl->edge->from_node->outgoing_e == NULL) {
	    enl->edge->from_node->outgoing_e = ne;
	    enl->edge->from_node->outgoing_etail = ne;
	} else {
	    enl->edge->from_node->outgoing_etail->next = ne;
	    enl->edge->from_node->outgoing_etail = ne;
	}

	enl->edge->from_node->outdegree++;

	ne = dp_calloc(1, sizeof(struct gml_elist));

	ne->edge = enl->edge;

	/* list of incoming edges */
	if (enl->edge->to_node->incoming_e == NULL) {
	    enl->edge->to_node->incoming_e = ne;
	    enl->edge->to_node->incoming_etail = ne;
	} else {
	    enl->edge->to_node->incoming_etail->next = ne;
	    enl->edge->to_node->incoming_etail = ne;
	}

	enl->edge->to_node->indegree++;

	enl = enl->next;
    }

    return;
}

/* clear all st lists
 * this is needed at refresh of in/out edges data
 * and only needed when the graph data has changed.
 */
void clear_stlist_all(struct gml_graph *g)
{
    struct gml_nlist *lnll = NULL;

    /* clear in every node */
    lnll = g->nodelist;
    while (lnll) {
	clear_stlist(lnll->node);
	lnll = lnll->next;
    }

    return;
}

/* clear the s/t list of a node */
void clear_stlist(struct gml_node *node)
{
    struct gml_elist *ell = NULL;
    struct gml_elist *ellnext = NULL;

    /* free outgoing edges */
    ell = node->outgoing_e;
    while (ell) {
	ellnext = ell->next;
	ell = dp_free(ell);
	if (ell) {
	}
	ell = ellnext;
    }

    node->outgoing_e = NULL;
    node->outgoing_etail = NULL;
    node->outdegree = 0;

    /* free incoming edges */
    ell = node->incoming_e;
    while (ell) {
	ellnext = ell->next;
	ell = dp_free(ell);
	if (ell) {
	}
	ell = ellnext;
    }

    node->incoming_e = NULL;
    node->incoming_etail = NULL;
    node->indegree = 0;

    return;
}

/* end. */
